package com.asia.algorithmcode.dynamicProgram;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @DESCRIPTION: 120、三角形最小路径和
 * @USER: wanfu
 * @DATE: 2025/5/26 星期一 16:23
 */
public class MinimumTotal {


    public static void main(String[] args) {
        List<Integer> l1 = Arrays.asList(-1);
        List<Integer> l2 = Arrays.asList(2, 3);
        List<Integer> l3 = Arrays.asList(1, -1, -3);

        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(l1);
        triangle.add(l2);
        triangle.add(l3);

        int i = new MinimumTotal().minimumTotal(triangle);

        System.out.println();
    }

    /**
     * O(n)的空间，动态规划
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] resList = new int[n];
        resList[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            resList[i] = resList[i - 1] + triangle.get(i).get(i);
            for (int j = i - 1; j > 0; j--) {
                resList[j] = Math.min(resList[j], resList[j]) + triangle.get(i).get(j);
            }
            resList[0] += triangle.get(i).get(0);
        }
        int min = resList[0];
        for (int i = 0; i < n; i++) {
            min = Math.min(min, resList[i]);
        }
        return min;
    }


}
